package com.frank.leetcode.question_16_20;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/4sum/description/
 * 18. 四数之和
 * 难度: 中等
 * <p>
 * <p>
 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
 * <p>
 * 注意：
 * <p>
 * 答案中不可以包含重复的四元组。
 * <p>
 * 示例：
 * <p>
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 * <p>
 * 满足要求的四元组集合为：
 * [
 * [-1,  0, 0, 1],
 * [-2, -1, 1, 2],
 * [-2,  0, 0, 2]
 * ]
 * <p>
 * <p>
 * Created by zhy on 2018/8/15.
 */
public class FourSum {
    private static Logger LOG = LoggerFactory.getLogger(FourSum.class);

    @Test
    public void run() {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        int target = -1;
        System.out.println(fourSum(nums, target));
    }


    private List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();

        int index = 0;


        while (index < nums.length - 3) {
            int n = index + 1;
            while (n < nums.length - 2) {
                int m = n + 1;
                while (m < nums.length - 1) {
                    int l = m + 1;
                    while (l < nums.length) {
                        LOG.info("*************************************left:{},start:{},end:{},right:{}", index, n, m, l);
                        int sum = nums[index] + nums[n] + nums[m] + nums[l];
                        if (sum == target) {
                            LOG.info("----------------------------------------");
                            LOG.info("left:{},start:{},end:{},right:{}", index, n, m, l);
                            LOG.info("sum:{},left:{},start:{},end:{},right:{}", sum, nums[index], nums[n], nums[m], nums[l]);

                            List<Integer> num = new ArrayList<>();
                            num.add(nums[index]);
                            num.add(nums[n]);
                            num.add(nums[m]);
                            num.add(nums[l]);
                            lists.add(num);
                            break;
                        } else if (sum > target) {
                            break;
                        } else {
                            l++;
                            while (l < nums.length && nums[l] == nums[l - 1]) {
                                l++;
                            }
                        }
                    }
                    m++;
                    while (m < nums.length - 1 && nums[m] == nums[m - 1]) {
                        m++;
                    }
                }
                n++;
                while (n < nums.length - 2 && nums[n] == nums[n - 1]) {
                    n++;
                }
            }
            index++;
            while (index < nums.length - 3 && nums[index] == nums[index - 1]) {
                index++;
            }
        }
        return lists;
    }


    public List<List<Integer>> fourSum_best(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        if (null == nums || nums.length < 4) {
            return ans;
        }

        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }
                if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                    break;
                }
                if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;

                while (left < right) {
                    int sum = nums[i] + nums[left] + nums[right] + nums[j];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        List<Integer> oneAnswer = Arrays.asList(nums[i], nums[left], nums[right], nums[j]);
                        ans.add(oneAnswer);
                        do {
                            left++;
                        } while (left < right && nums[left - 1] == nums[left]);

                        do {
                            right--;
                        } while (left < right && nums[right] == nums[right + 1]);
                    }
                }
            }
        }
        return ans;
    }
}